package cn.bellychang.binarytree.liuxin;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: bellychang
 * @date: 2020/2/23
 */
public class BinarySearchTree<E extends Comparable> {

    private BinaryTreeNode<E> root;

    private int size;

    /**
     * 如何处理高度 是一个问题
     */
    private int height;

    public BinarySearchTree() {
    }

    public BinaryTreeNode<E> getRoot() {
        return root;
    }

    public E findMin() {
        checkEmpty();
        BinaryTreeNode<E> temp = root;
        while (temp.left != null) {
            temp = temp.left;
        }
        return temp.getData();
    }

    private void checkEmpty() {
        if (size == 0) {
            throw new IllegalArgumentException("this tree is empty");
        }
    }

    public E findMax() {
        checkEmpty();
        BinaryTreeNode<E> temp = root;
        while (temp.right != null) {
            temp = temp.right;
        }
        return temp.getData();
    }

    public int getHeight() {
        return height;
    }

    public void insert(E e) {
        BinaryTreeNode<E> treeNode = new BinaryTreeNode<>(e);
        if (size == 0) {
            root = treeNode;
            height++;
        } else {
            TwoTuple<BinaryTreeNode<E>, Integer> parentNodeTuple = findParentNode(treeNode);
            if (parentNodeTuple.first.getData().compareTo(treeNode.getData()) > 0) {
                parentNodeTuple.first.left = treeNode;
            } else {
                parentNodeTuple.first.right = treeNode;
            }
            // TODO:仅仅当这一层第一个节点 height++
        }
        size++;
    }

    /**
     * 并不需要返回当前ParentTreeNode的height
     *
     * @param treeNode
     * @return
     */
    private TwoTuple<BinaryTreeNode<E>, Integer> findParentNode(BinaryTreeNode<E> treeNode) {
        int parentNodeHeight = 1;
        BinaryTreeNode<E> parentNode = root;
        while (parentNode != null) {
            if (parentNode.getData().compareTo(treeNode.getData()) > 0 && parentNode.left != null) {
                parentNode = parentNode.left;
            } else if (parentNode.getData().compareTo(treeNode.getData()) < 0 && parentNode.right != null) {
                parentNode = parentNode.right;
            } else if (parentNode.right == null) {
                break;
            } else if (parentNode.left == null) {
                break;
            }
            parentNodeHeight++;
        }
        return Tuple.createTuple(parentNode, parentNodeHeight);
    }

    /**
     *
     * @param e
     * @return no found return null
     */
    public BinaryTreeNode<E> find(E e) {
        BinaryTreeNode<E> newTreeNode = new BinaryTreeNode<>(e);
        BinaryTreeNode<E> current = root;
        while (current != null) {
            if (current.getData().compareTo(newTreeNode.getData()) > 0) {
                current = current.left;
            } else if (current.getData().compareTo(newTreeNode.getData()) < 0) {
                current = current.right;
            } else {
                return current;
            }
        }
        return null;
    }

    List<E> list = new ArrayList<>();

    public List<E> traverseInOrder() {
        list.clear();
        checkEmpty();
        traverseInOrderRecursion(root);
        return list;
    }

    public List<E> traversePreOrder() {
        list.clear();
        checkEmpty();
        traversePreOrderRecursion(root);
        return list;
    }


    public List<E> traversePostOrder() {
        list.clear();
        checkEmpty();
        traversePostOrderRecursion(root);
        return list;
    }

    private void traversePostOrderRecursion(BinaryTreeNode<E> treeNode) {
        if (treeNode.left != null) {
            traversePostOrderRecursion(treeNode.left);
        }
        if (treeNode.right != null) {
            traversePostOrderRecursion(treeNode.right);
        }
        list.add(treeNode.getData());
    }


    private void traversePreOrderRecursion(BinaryTreeNode<E> treeNode) {
        list.add(treeNode.getData());
        if (treeNode.left != null) {
            traversePreOrderRecursion(treeNode.left);
        }
        if (treeNode.right != null) {
            traversePreOrderRecursion(treeNode.right);
        }
    }


    private void traverseInOrderRecursion(BinaryTreeNode<E> treeNode) {
        if (treeNode.left != null) {
            traverseInOrderRecursion(treeNode.left);
        }
        // basic lockcondition
        list.add(treeNode.getData());
        if (treeNode.right != null) {
            traverseInOrderRecursion(treeNode.right);
        }
    }

    @Override
    public String toString() {
        BinaryTreeNode<E> temp = root;
        while (temp != null) {
            temp = temp.left;
        }
        return null;
    }

    public int getSize() {
        return size;
    }

    /**
     * 仅仅能处理叶子节点
     * @param e
     */
    public BinaryTreeNode<E> remove(E e) {
        if (size <= 0) {
            throw new IllegalArgumentException("this value does not exist in the binary search tree");
        }
        // judge this node exist in the tree
        // judge leaf node or intermediate node
        BinaryTreeNode<E> newTreeNode = new BinaryTreeNode<>(e);
        BinaryTreeNode<E> parentNode = root;
        BinaryTreeNode<E> temp = root;
        while (temp != null) {
            if (temp.getData().compareTo(newTreeNode.getData()) > 0 && temp.left != null) {
                parentNode = temp;
                temp = temp.left;
            } else if (temp.getData().compareTo(newTreeNode.getData()) == 0) {
                if (TreeNodeStatus.LEAF_NODE==checkTreeNodeStatus(temp)) {
                    // leaf node
                    if (parentNode.getData().compareTo(temp.getData()) > 0) {
                        parentNode.left = null;
                    } else {
                        parentNode.right = null;
                    }
                } else if (TreeNodeStatus.INTERMEDIATE_NODE_WITH_ONE_CHILD == checkTreeNodeStatus(temp)) {
                    // handle boundary lockcondition: removed treenode is root
                    if (root.getData().compareTo(newTreeNode.getData()) == 0) {
                        if (root.left != null) {
                            root = root.left;
                        } else {
                            root = root.right;
                        }
                    }
                    // with one child
                    if (parentNode.getData().compareTo(temp.getData()) > 0) {
                        if (temp.left != null) {
                            parentNode.left = temp.left;
                        } else {
                            parentNode.left = temp.right;
                        }
                    } else {
                        if (temp.left != null) {
                            parentNode.right = temp.left;
                        } else {
                            parentNode.right = temp.right;
                        }
                    }
                } else {
                    // temp的right就是后继节点
                    if (temp.right.left == null) {
                        parentNode.right = temp.right;
                        parentNode.right.left = temp.left;
                    } else {
                        BinaryTreeNode<E> successor = temp.right;
                        BinaryTreeNode<E> successorParent = successor;
                        while (successor.left != null) {
                            successorParent = successor;
                            successor = successor.left;
                        }

                        // sequence is important
                        successorParent.left = successor.right;

                        parentNode.right = successor;
                        parentNode.right.left = temp.left;
                        parentNode.right.right = successorParent;
                    }
                }
                size--;
                // TODO: 仅仅当这一层最后一个节点 height--
                break;
            } else if (temp.getData().compareTo(newTreeNode.getData()) < 0 && temp.right != null) {
                parentNode = temp;
                temp = temp.right;
            } else if (temp.left == null) {
                throw new IllegalArgumentException("this value does not exist in the binary search tree");
            } else if (temp.right == null) {
                throw new IllegalArgumentException("this value does not exist in the binary search tree");
            }
        }
        return temp;
    }

    private BinaryTreeNode<E> getSuccessor(BinaryTreeNode<E> treeNode) {
        BinaryTreeNode<E> parentTreeNode = treeNode;
        BinaryTreeNode<E> current = treeNode.right;
        while (current != null) {
            if (current.left != null) {
                current = current.left;
                parentTreeNode = current;
            }
        }
        return current;
    }

    private TreeNodeStatus checkTreeNodeStatus(BinaryTreeNode<E> treeNode) {
        if (treeNode.left == null && treeNode.right == null) {
            return TreeNodeStatus.LEAF_NODE;
        } else if (treeNode.left != null && treeNode.right != null) {
            return TreeNodeStatus.INTERMEDIATE_NODE_WITH_TWO_CHILDREN;
        } else {
            return TreeNodeStatus.INTERMEDIATE_NODE_WITH_ONE_CHILD;
        }
    }
}

enum TreeNodeStatus{LEAF_NODE,INTERMEDIATE_NODE_WITH_ONE_CHILD,INTERMEDIATE_NODE_WITH_TWO_CHILDREN}
